#include "../tools.h"


class Solution {
public:
    bool check(const vector<int>& route, int pos, int n){
        int cur_col, cur_row;
        // 左上
        cur_col = pos;
        cur_row = route.size();
        while(cur_row > 0 && cur_col > 0){
            if(--cur_col == route[--cur_row]) return false;
        }
        // 右上
        cur_col = pos;
        cur_row = route.size();
        while(cur_row > 0 && cur_col <= n){
            if(++cur_col == route[--cur_row]) return false;
        }
        return true;
    }

    void backtrack(vector<vector<int>>& res, vector<int>& route, vector<bool>& flag, int n){
        if(route.size() == n){
            res.push_back(route);
        }
        
        for(int i = 0; i < n; ++i){
            if(!flag[i] && check(route, i, n)){
                route.push_back(i);
                flag[i] = true;
                backtrack(res, route, flag, n);
                route.pop_back();
                flag[i] = false;
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<int>> res;
        // if(n == 1) return res;

        vector<bool> flag(n, false);
        vector<int> route;
        backtrack(res, route, flag, n);

        // for(auto e: res){
        //     show(e);
        // }


        vector<vector<string>> res_str;
        char tmp[n + 1]; fill(tmp, tmp + n, '.'); tmp[n] = '\0';
        for(int i = 0; i < res.size(); ++i){
            vector<string> res_str_one;
            for(int j = 0; j < res[i].size(); ++j){
                tmp[res[i][j]] = 'Q';
                res_str_one.push_back(tmp);
                tmp[res[i][j]] = '.';
            }
            res_str.push_back(res_str_one);
        }

        return res_str;
        
    }
};

int main(int argc, char const *argv[])
{
    Solution sol;

    int n = 4;
    auto res = sol.solveNQueens(n);
    for(auto e: res){
        for(auto ee: e)
            cout << ee << " ";
        cout << endl;
    }



    return 0;
}
